import heapq
from typing import List


class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        heap = [(nums1[0] + nums2[0], (0, 0))]
        ans = []
        visited = set()
        for t in range(k):
            v, (p1, p2) = heapq.heappop(heap)
            ans.append([nums1[p1], nums2[p2]])
            for d1, d2 in [(p1 + 1, p2), (p1, p2 + 1)]:
                if (d1, d2) in visited: continue
                if d1 >= len(nums1) or d2 >= len(nums2): continue
                visited.add((d1, d2))
                heapq.heappush(heap, (nums1[d1] + nums2[d2], (d1, d2)))
        return ans


if __name__ == '__main__':
    s = Solution()
    r = s.kSmallestPairs([1, 2, 4, 5, 6], [3, 5, 7, 9], 20)
    print(r)
